#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <math.h>  
#include <queue>
#include <vector>
#include <stdio.h>
#include <sys/select.h>

#define INF (0x23333333)  
#define MAXN (302)
#define random(x) (rand()%x)

using namespace std;

int g[MAXN][MAXN]; //已用代价，参数为行列坐标  
int h[MAXN][MAXN]; //估计还需代价，参数为行列坐标 
const int dl[] = {1,-1,0,0};  
const int dc[] = {0,0,-1,1}; 
bool in_close[MAXN][MAXN]; 
bool in_open[MAXN][MAXN]; 

/*坐标点结构体*/
struct point  
	{  
		int l,c;  
		point(){}  
		point(int _l, int _c){l=_l;c=_c;}  
		bool operator<(const point &o) const  
		{  
			return g[l][c]+h[l][c]>g[o.l][o.c]+h[o.l][o.c];  
		} 
	};
point path[MAXN][MAXN]; 

class Spirit{
	
	public:
		Spirit()
		{
			m=20,n=40;
			
			tl2=20,tc2=40;
			tl3=20,tc3=40;
			tl4=20,tc4=40;
			tl5=20,tc5=40;
			tl6=1, tc6=1;
			tl7=1, tc7=1;
			tl8=1, tc8=1;
			tl9=1, tc9=1;

		}
		void sleep_ms(unsigned int secs);//微秒延时函数
		void new_space(int m1, int n1);//分配空间
		void delete_space(int m1);//释放空间
		void Maze_Runner(int tlpos,int tcpos,int nlpos,int ncpos,int num);//移动精灵
		void Building_labyrinth();//创建迷宫
		void print_res();//位置更新
		void find_path(int tl,int tc,int sl,int sc,int sp);//寻路算法
		void Clear(int num);//初始化坐标值
		void Computing_path();//刷新位置

	private:
		int **p;//定义一个二维的int数组
		int m,n;
		int tl2,tc2;
		int tl3,tc3;
		int tl4,tc4;
		int tl5,tc5;
		int tl6,tc6;
		int tl7,tc7;
		int tl8,tc8;
		int tl9,tc9;
};

void Spirit::sleep_ms(unsigned int secs)
{
    struct timeval tval;
    tval.tv_sec=secs/1000;
    tval.tv_usec=(secs*1000)%1000000;
    select(0,NULL,NULL,NULL,&tval);
}

	 /* 分配空间*/
void Spirit::new_space(int m1, int n1)
{
	m=m1;
	n=n1;
	p=new int*[m+2];//创建行指针
	for(int i=0;i<=m+1;i++){//为每一行分配空间
	p[i] = new int [n+2];}
}
/*释放空间*/
void Spirit::delete_space(int m1)
{
	m=m1;
	for(int i=0;i<=m+1;i++){
		delete[] p[i];}
		delete[] p;
}

/*创建迷宫*/
void Spirit::Building_labyrinth()
{
	srand((int)time(0));
	for(int i=0;i<=m+1;i++)
		for(int j=0;j<=n+1;j++)
		{
			if(i==0|j==0|i==m+1|j==n+1)
				p[i][j]=1;
			else if(i>=1&&i<=5&&j>=1&&j<=2||i>=m-5&&i<=m&&j>=n-2&&j<=n)
				p[i][j]=0;
			else
			{
				int x=random(50);
				if(x<=1)
					p[i][j]=1;
				else
					p[i][j]=0;	
			}
		}		
		
} 
/*初始化坐标值*/
void Spirit::Clear(int num)
{
	int i,j;
    for(i = 1; i <= m; i++)  
		for(j = 1; j <= n; j++){			
         if( p[i][j]==num)
           p[i][j]=0;
		}
}

/*移动精灵*/
void Spirit::Maze_Runner(int tlpos,int tcpos,int nlpos,int ncpos,int num)
{
		int ll,cc;
		int x,y;
		
		ll=tlpos;
		cc=tcpos;
		find_path(tlpos,tcpos,nlpos,ncpos,num); 
		x=path[ll][cc].l;
		y=path[ll][cc].c;
		//cout<<"x y  "<<x<<"  "<<y<<endl;
		Clear(num);
		p[ll][cc]=num;
		if(num==2){tl2=x;tc2=y;cout<<"x1 y1  "<<x<<"  "<<y<<endl;}
		else if(num==3){tl3=x;tc3=y;cout<<"x2 y2  "<<x<<"  "<<y<<endl;}
		else if(num==4){tl4=x;tc4=y;cout<<"x3 y3  "<<x<<"  "<<y<<endl;}
		else if(num==5){tl5=x;tc5=y;cout<<"x4 y4  "<<x<<"  "<<y<<endl;}
		else if(num==6){tl6=x;tc6=y;cout<<"xA yA  "<<x<<"  "<<y<<endl;}
		else if(num==7){tl7=x;tc7=y;cout<<"xB yB  "<<x<<"  "<<y<<endl;}
		else if(num==8){tl8=x;tc8=y;cout<<"xC yC  "<<x<<"  "<<y<<endl;}
		else if(num==9){tl9=x;tc9=y;cout<<"xD yD  "<<x<<"  "<<y<<endl;}
} 
/*A星寻路算法*/
void Spirit::find_path(int tl,int tc,int sl,int sc,int sp)  
{  
	int i,j; 
    int	l,c;
    int cl,cc,nl,nc; //cl,cc当前处理的点的位置， nl,nc当前处理的点的邻居的位置
	//优先队列，对头元素最大
	priority_queue<point> open_list;
    for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			path[i][j]=point(i,j);//初始化路径

	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
	 		 in_close[i][j] = false;  //初始化关闭列表
	
	//if(p[sl][sc]!=0 || p[tl][tc]!=0)return; //出发点或者目标点不可通行，返回	
    for(i = 1; i <= m; i++)  
        for(j = 1; j <= n; j++)  
        {  
            h[i][j] = (int)sqrt((double)(i-tl)*(i-tl)+(double)(j-tc)*(j-tc))+1;//估计代价 = 这个点到目标点的几何距离向上取整    
            g[i][j] = INF;//已用代价初始化为INF  
        }  
		
    g[sl][sc] = 0; //出发点扔到open_list
    in_open[sl][sc] = true;  
    open_list.push(point(sl,sc));  
      
    while(open_list.size())  
    {  
        cl = open_list.top().l;  
        cc = open_list.top().c;  
        open_list.pop();  
        if(cl == tl && cc == tc)  
            break;  	//找到目标，跳出循环  
       
		 //当前点算入关闭列表中  
        in_close[cl][cc] = true;  
        for(i = 0; i < 4; i++)  
        {  
            nl = cl+dl[i];  
            nc = cc+dc[i];  
            if(p[nl][nc]!=0)continue; 	  //不可通行  
			if(in_close[nl][nc])continue; //在关闭列表 
			if(! in_open[nl][nc])  
            {     //发现新节点 
                open_list.push(point(nl,nc));  
            }else if(g[cl][cc]+1 >= g[nl][nc])  
                continue; //不是更好的解，continue 
			
			//找到一个更优的解，记录路径，更新g值  
            path[nl][nc] = point(cl,cc);  
            g[nl][nc] = g[cl][cc] + 1;  
        }  
    } 
	l = tl;  
    c = tc; 
	while(true)
    {
		if(i == sl && j == sc)
			break;  
       i = path[l][c].l;  
       j = path[l][c].c;  
        l = i;  
        c = j;
	}
}  
/*刷新位置*/
void Spirit::Computing_path()
{ 	
	int count=0;
	while(1)
		{	
			++count;
			printf("\033[2J");
			
			if((count>16&&(count-16)%5==0)){//精灵D和4
				Maze_Runner(tl5,tc5,1,1,5);
				Maze_Runner(tl9,tc9,20,40,9);}
			if((count>12&&(count-12)%4==0)){//精灵C和3
				Maze_Runner(tl4,tc4,1,1,4);
				Maze_Runner(tl8,tc8,20,40,8);}
			if((count>7)&&((count-7)%3==0)){//精灵B和2
				Maze_Runner(tl3,tc3,1,1,3);
				Maze_Runner(tl7,tc7,20,40,7);}
			if((count>1)&&((count-1)%2==0)){//精灵A和1
				Maze_Runner(tl2,tc2,1,1,2);
				Maze_Runner(tl6,tc6,20,40,6);}
				
			if(p[1][1]==5&&p[n][m]==9 ){
				break;
				cout<<"Game over"<<endl;
				 }
			print_res();
			 
			sleep_ms(200);
		}	
}	
/*打印显示*/
void Spirit::print_res()
{
	for(int i=0;i<=m+1;i++)
	{
		for(int j=0;j<=n+1;j++)
			switch(p[i][j])
			{
				case 0:cout<<" ";break;
				case 1:cout<<"#";break;
				case 2:cout<<"\033[41m1\033[m";break;
				case 3:cout<<"\033[41m2\033[m";break;
				case 4:cout<<"\033[41m3\033[m";break;
				case 5:cout<<"\033[41m4\033[m";break;
				case 6:cout<<"\033[42mA\033[m";break;
				case 7:cout<<"\033[42mB\033[m";break;
				case 8:cout<<"\033[42mC\033[m";break;
				case 9:cout<<"\033[42mD\033[m";break;
				default:break;
			}
		cout<<endl;
	}
}

int main()
{
	//定义一个精灵对象
	Spirit Smurfs;
	int m1=20,n1=40;
	//cout<<"请输入迷宫规格：";
	//cin>>m1>>n1;
	Smurfs.new_space(m1,n1);//分配空间
	Smurfs.Building_labyrinth();//创建迷宫
	Smurfs.Computing_path();//刷新位置
	Smurfs.delete_space(m1);//释放空间
	return 0;
}
